package dichotomy.isprefectnum;
/**
 * @Date 2020/1/23
 * @author 王光浩
 * @Need 给出一个整数，判断该数是否是一个完全平方数，如果是则返回true，否则返回false。
 * @Thinking 使用牛顿迭代法。思路大致如下：构建一个函数关于y=x^2-num，我们需要找的是当y=0时且x>0时x的值
 *           。在该迭代法中，首先设置一个临界值x1（这个临界值的平方大于等于num），然后找下一个临界值x2，下一个
 *           临界值的算法如下：x2=1/2(x1+num/x1)，当x=x1时，在函数上做一条切线，该切线与x轴的交点就是x2，然后
 *           更新x1=x2，并判断x1的平方是否小于等于num，如果是则结束迭代，最后判断x1的平方是否等于num即可。
 *           复杂度分析：时间复杂度O（logn），空间复杂度O（1）
 */
public class OtherMethodTwo {
	public boolean isPerfectSquare(int num) {
		if(num<2)return true;
		long x=num/2;
		while(x*x>num) {
			x=(x+num/x)/2;
		}
		return x*x==num;
	}

}
